//https://leetcode.cn/problems/binary-tree-cameras/
package codeRandomThoughts.Test968监控二叉树;

import codeRandomThoughts.utils.TreeNode;

public class Solution {
    int result = 0;

    public int minCameraCover(TreeNode root) {
        //从底部向上,让叶子结点的父节点安摄像头,所用摄像头最少
        //先给叶子结点的父节点放个摄像头,然后隔两个结点放一个摄像头,直到二叉树头节点
        //每个结点有三种状态
        //0 该结点无覆盖
        //1 本节点有摄像头
        //2 本节点有覆盖

        //遍历树的过程中会遇到空结点,空结点是什么状态?
        //空结点只能是有覆盖,如果是无覆盖,我就要给叶子结点安装摄像头了
        //if (root.val == 0) result++;
        if (traversal(root) == 0) result++;
        return result;
    }

    /**
     * 后序遍历
     *
     * @param root 二叉树的根节点
     * @return 每个节点对应的状态 0无覆盖 1有监控 2有覆盖
     */
    public int traversal(TreeNode root) {
        //空结点,该结点为有覆盖
        if (root == null) return 2;

        int left = traversal(root.left);
        int right = traversal(root.right);

        if (left == 2 && right == 2) {
            //情况1
            //左右结点都有覆盖
            return 0;
        } else if (left == 0 || right == 0) {
            //情况2
            // 左右至少有一个无覆盖
            result++;
            return 1;
        } else if (left == 1 || right == 1) {
            //情况3
            //左右至少有一个摄像头
            return 2;
        }

        return 0;//这一句永远运行不到 只是为了易读性
    }
}
